import random

def quick(lst):
    if len(lst)<=1:
        return lst
    i = 1
    j = len(lst)-1
    while True:
        while i<=j and lst[i]<=lst[0]:
            i+=1
        while i<=j and lst[j]>=lst[0]:
            j-=1

        if i>j: # 分割完成，交错
            break
        elif i == j: 
            if lst[i]<=lst[0]:
                j+=1
                i+=1
            else:
                j-=1
                i-=1
        else:
            lst[i],lst[j]=lst[j],lst[i]

    left = quick(lst[1:j+1])
    right = quick(lst[i:])

    result = list()
    result.extend(left)
    result.append(lst[0])
    result.extend(right)
    return result

if __name__ == "__main__":
    n = 1000
    lst = list({random.randrange(n,10*n-1) for _ in range(n)})
    print(quick(lst)==sorted(lst))
    # print(lst)
